НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №2
з навчальної дисципліни “Програмування складних алгоритмів”
На тему
«Рекурсивні алгоритми»
Варіант 21
Київ 2022
Мета роботи: набуття практичних навичок з рекурсивними функціями.
Завдання до лабораторної роботи:
Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.
/
Рисунок 1. Завдання для варіанту 21
Теоретична частина
Рекурсiєю називається такий спосiб органiзацiї обробки даних, при якому програма (функцiя) викликає сама себе безпосередньо, або з iнших програм (функцiй).
Рекурсивний алгоритм – це алгоритм, в описі якого прямо або побічно міститься звернення до самого себе.
Рекурсивний метод в програмуванні – як альтернативний по відношенню до ітераційного.
Основні відмінності між рекурсією та ітерацією:
Рекурсивний метод містить набір інструкцій, сам виклик оператора і умову завершення, тоді як заяви ітерації містять ініціалізацію, приріст, стан, набір команд в межах циклу і керуючу змінну.
Умовний оператор вирішує припинення значення рекурсії і значення змінної керування, що визначає припинення операції ітерації.
Якщо метод не призводить до умови завершення, то він входить до нескінченної рекурсії. З іншого боку, якщо керуюча змінна ніколи не призводить до значення завершення, оператор ітерації повторюється нескінченно.
Нескінченна рекурсія може призвести до збою системи, тоді як нескінченна ітерація споживає процесори.
Рекурсія завжди застосовується до методу, тоді як ітерація застосовується до набору інструкцій.
Змінні, створені під час рекурсії, зберігаються на стеку, тоді як ітерація не вимагає стека.
Рекурсія викликає накладні витрати на повторне виклик функції, тоді як ітерація не має функції виклику накладних витрат.
Завдяки функції, що викликає накладні витрати, виконання рекурсії відбувається повільніше, тоді як виконання ітерації відбувається швидше.
Рекурсія зменшує розмір коду, тоді як ітерації роблять код довшим.
Складність алгоритму (в обох випадках розраховується за формулою O(N))
n
Кількість ітерацій
Час виконання (в ms)
З використанням рекурсії
10
10
0.0282
50
50
0.03012
100
100
0.03095
Без використання рекурсії
10
10
0.00056
50
50
0.00263
100
100
0.00531
/
Рисунок 2. Залежність часу виконання алгоритму від n
Результат
/
Рисунок 3. Скріншот результату програми
Перевірка результату
/
Висновок
У процесі виконання лабораторної роботи набуто практичних навичок з рекурсивними функціями, розроблено програму з використанням рекурсивної функції та без використання рекурсії.
Оцінено час виконання та складність алгоритму, в результаті чого зроблено висновок, що алгоритм без використання рекурсії працює швидше, однак бувають випадки, коли вирішення задачі рекурсивно простіше в плані обсягу коду та відладки.
Код програми
#include <iostream>
#include <cmath>
#include <chrono>
double withRec(int i, int n, double recursion) {
if(i<=n)
return withRec(i+1, n, recursion * ((2*i+1)/(pow(i, 3))));
return recursion;
}
int main(){
int i;
double f1;
double f2 = 1;
int n = 0;
std::cout << "Задайде i, перше значення: ";
std::cin >> i;
std::cout << "Задайте n, останнє значення: ";
std::cin >> n;
if (n <= 0)
std::cout << "Помилка! Введіть допустиме значення/n";
auto start = std::chrono::high_resolution_clock::now();
f1 = withRec(i, n, 1);
std::chrono::duration<double, std::milli> time1 = std::chrono::high_resolution_clock::now() - start;
start = std::chrono::high_resolution_clock::now();
for (int i = 1; i <= n; i++) {
f2 = f2 * ((2*i+1)/(pow(i, 3)));
}
std::chrono::duration<double, std::milli> time2 = std::chrono::high_resolution_clock::now() - start;
std::cout << "\nДобуток ряду від 1 до " << n << " по формулі (2i+1)/i^3\n";
std::cout...
